#Pollard p-1 算法

import random
import math

def pollard(n):
    b = random.randint(2,n-1)
    g = gcd(b,n)
    if g >= 2:
        return g
    else:
        g = find(n,b)
        if g == -1:
            print("false")
            return
        else:
            return g


#b > a
def gcd(a,b):
    if b%a == 0:
        return a
    else:
        return gcd(b%a, a)

def find(n,b):
    prime = [2,3,5,7,11,13]
    for q in prime:
        l = floor(q,n)
        tmp = pow(q,l)
        b = mypow(b,tmp,n)
        g = gcd(b-1, n)
        if g >1 and g < n:
            return g
        elif g == 1:
            pass
        else:
            return -1
    return -1

def mypow(a,b,n):
    tmp = 1
    while b > 0:
        if b % 2 == 1:
            tmp = tmp*a%n
        a = a*a%n
        b = math.floor(b/2)
    return tmp


def floor(p,n):
    i = 0
    t = 1
    while t < n:
        t = t*p
        i += 1
    i -= 1
    return i
        



